///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Contains source code from the article "Radix Sort Revisited".
 *	\file		RadixSort.h
 *	\author		Fish
 *	\date		July 17, 2011
 *  \brief      Based on Pierre Terdiman's IceRevistedRadix
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Include Guard
#ifndef RADIXSORT_H
#define RADIXSORT_H

// Headers
#include "mytypes.h"
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 * \enum       RadixHint
 * \brief      Radix hint tells function how to sort...
 */
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    enum RadixHint
    {
        RADIX_SIGNED,       //!< Input values are signed
        RADIX_UNSIGNED      //!< Input values are unsigned
    };


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 * \class       CSAP_Element
 * \brief       Used for managing entires in CSAP_PairManager
 */
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    class RadixSort
    {
        public:
                                        RadixSort();
                                        ~RadixSort();

        // Sorting methods
                RadixSort&              Sort(const uint* input, uint nb, RadixHint hint=RADIX_SIGNED); // Sorts backwards >_>
                RadixSort&              Sort(const float* input, uint nb);

        //! Returns the list of indicies in sorted order; can further sort the data if needed
        inline uint*                    GetRanks()      const   { return ranks_;      }

        //! Returns the total number of calls to radix sorter
        inline uint                     GetCallCount()  const   { return totalCalls_; }
        
        inline uint                     GetSize()       const   { return currentSize_; }

        private:
//                uint*                   histogram_;             //!< Counters for each byte
//                uint*                   offset_;                //!< Offsets (nearly a cummulative distribution function?)

                uint                    currentSize_;           //!< Current size of indicies list
                uint*                   ranks_;                 //!< Two lists, swapped with each pass
                uint*                   ranks2_;

                uint                    totalCalls_;            //!< Total # of calls to sort routine
        // Internal methods
         inline void                    CheckResize(uint nb);
         inline bool                    Resize(uint nb);
    };

#endif // RADIXSORT_H
